{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# 解决3n+1问题\n",
    "## Collatz-Odd-Tree通过h(x)=4x+1和v(x)=(2x-1)/3 or (4x-1)/3迭代生成所有正奇数\n",
    "Cody Luo(cody@ustc.edu) 2019-10-28, 2019-11-17 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**3n+1 问题(3n+1 Problem)** 是 L. Collatz 在 1937 年提出的一个猜想, 也叫 **Collatz 猜想**, 或者被称作 3n+1 归一映射(3x+1 Mapping)。 3n+1 问题是如此的著名于世，因为它几乎可以让小学一年级学生领会理解，更是数学爱好者们的起步之题，并且被多个数学家提及，如 Hasse 算法, Kakutani 问题, Syracuse 算法, Thwaites 猜想(Thwaites conjecture), Ulam 问题（Ulam's problem, Lagarias 1985)……\n",
    "Thwaites (1996) 已经悬赏 £1000 为解决 3n+1 猜想.\n",
    "\n",
    "**3n+1 问题** 的描述十分简单： 定义递推数组 `a[0]:=n`, k=0,1,2,3,..., `a[k+1]= 3*a[k]+1 如果a[k]是奇数, a[k+1]= a[k]/2 如果a[k]是偶数`... 猜想说对于任意正整数n,数组总会在有限步之内取得 1。 然后[1,4,2,1,4,2,...]不停循环下去。\n",
    "\n",
    "```\n",
    "a[0]:=n ,\n",
    "a[k+1]:= 3*a[k]+1 if is_odd(a[k])\n",
    "a[k+1]:= a[k]/2   elif is_even(a[k]) , for k=0,1,2,3,...\n",
    "\n",
    "def f(x):= 3*x+1 if x%2==1 else x//2\n",
    "a[k+1]:=f(a[k])\n",
    "\n",
    "# Syracuse function g(n)\n",
    "def g(n):\n",
    "    while n%2==0 : n/=2\n",
    "    n=3*n+1\n",
    "    while n%2==0 : n/=2\n",
    "    return n\n",
    "```\n",
    "\n",
    "Syracuse 函数(Syracuse function, g(x))对其做了简化处理，每次直接去掉其中的`2`的幂，因此 3n+1 问题也等同于说: 对于任意正奇数 n, 总存在有限步数 s1(n), 使 nest(g,s1,n)==1 .\n",
    "\n",
    "> sage.misc.misc.nest(f, n, x)  \n",
    "> Return f(f(...f(x)...)), where the composition occurs n times.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "3n+1 猜想证法 1：\n",
    "\n",
    "由递推归纳法的思想，我们只需证明：n 总会在有限步s0(n)次嵌套调用 g(x)之前便取得一个更小的奇数 m, m<n .显然，对于偶数 2k, 以及 4k+1 型的数即`(n*3+1) %4==0`的数 n 来说，调用g(n)一次便下降了。\n",
    "\n",
    "```\n",
    "g(2k)<=(k*3+1)/2<2k\n",
    "g(4k+1) <= ((4k+1)*3+1)/4 < 4k+1\n",
    "```\n",
    "\n",
    "对于 4k-1 型的数尤其还是3的倍数来说呢？存在下面的Collatz-Syracuse 函数下降定理。\n",
    "\n",
    " **Collatz-Syracuse Decent Theorem**: For any odd positive integer n=2*k+1, it exists s1,`s1<=g(n)<=(3*n+1)/2` to make `nest(g,s1,n)==1`;  \n",
    "Except n=27 or 31, it will get a less number m, m<n before `n` times iterately calling g(x). To be brief,  it exists `s0,s0<n` to make `m= nest(g,s0,n)<n` except n=27 or n=31;  \n",
    "(n,f(n),g(n),(3*n+1)/2,s(n))  \n",
    "(27, 82, 41, 41, (37, 41))  \n",
    "(31, 94, 47, 47, (35, 39))  \n",
    "\n",
    " **Collatz-Syracuse 函数下降定理** :  \n",
    " 对于任意正奇数 `n=2*k+1` 嵌套调用 g(x)，取到`1`的步数不会超过 `g(n)`。即存在s1, `s1<=g(n)<=(n*3+1)/2`, 使得nest(g,s1,n)==1；  \n",
    " 对于`27,31`之外的任意正奇数`n=2*k+1`,只需经过`s0, s0<n`次嵌套调用g(x), 总会取到一个比 n 更小的数m， `m=nest(g,s0,n)<n`。  \n",
    "(n,f(n),g(n),(3*n+1)/2,s(n))  \n",
    "(27, 82, 41, 41, (37, 41))  \n",
    "(31, 94, 47, 47, (35, 39))  \n",
    "\n",
    "注: 尝试证明有限步内下降，比起力图考察证明不存在的循环圈来说，显得更简单更直接更有力。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "38d0bd5e52bb46ecb9936a3fe5d3d776",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIGNvbGxhdHogYXQgMHg3ZjlkMDUyZmZkZTg+IHdpdGggMSB3aWRnZXQKICBuOiBUcmFuc2Zvcm1JbnRTbGlkZXIodmFsdWU9MSwgZGVzY3LigKY=\n"
      ]
     },
     "execution_count": 1,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(n):\n",
    "    return 3*n+1 if n%2==1 else n//2\n",
    "\n",
    "def g(n):\n",
    "    while n%2==0 : n/=2\n",
    "    n=3*n+1\n",
    "    while n%2==0 : n/=2\n",
    "    return n\n",
    "\n",
    "\"\"\"\n",
    "s(n): return (s0,s1)\n",
    "s0: the min steps s0 make nest(g,s0,n)<n\n",
    "s1: the min steps s1 make nest(g,s1,n)==1\n",
    "\"\"\"\n",
    "def s(n):\n",
    "    if n==1: return (0,0);\n",
    "    step,s0,s1=1,1,1\n",
    "    x=g(n)\n",
    "    while x>=n:\n",
    "        x=g(x)\n",
    "        step+=1\n",
    "    s0=step\n",
    "    while x>1:\n",
    "        x=g(x)\n",
    "        step+=1\n",
    "    s1=step\n",
    "    return (s0,s1)\n",
    "\n",
    "@interact\n",
    "def collatz(n=slider(1,500, step_size=2)):\n",
    "    result=(n,f(n),g(n),(3*n+1)/2,s(n))\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 4, 1, 2, (0, 0))\n",
      "(3, 10, 5, 5, (2, 2))\n",
      "(5, 16, 1, 8, (1, 1))\n",
      "(7, 22, 11, 11, (4, 5))\n",
      "(9, 28, 7, 14, (1, 6))\n",
      "(11, 34, 17, 17, (3, 4))\n",
      "(13, 40, 5, 20, (1, 2))\n",
      "(15, 46, 23, 23, (4, 5))\n",
      "(17, 52, 13, 26, (1, 3))\n",
      "(19, 58, 29, 29, (2, 6))\n",
      "(21, 64, 1, 32, (1, 1))\n",
      "(23, 70, 35, 35, (3, 4))\n",
      "(25, 76, 19, 38, (1, 7))\n",
      "(27, 82, 41, 41, (37, 41))\n",
      "(29, 88, 11, 44, (1, 5))\n",
      "(31, 94, 47, 47, (35, 39))\n",
      "(33, 100, 25, 50, (1, 8))\n",
      "(35, 106, 53, 53, (2, 3))\n",
      "(37, 112, 7, 56, (1, 6))\n",
      "(39, 118, 59, 59, (5, 11))\n",
      "(41, 124, 31, 62, (1, 40))\n",
      "(43, 130, 65, 65, (3, 9))\n",
      "(45, 136, 17, 68, (1, 4))\n",
      "(47, 142, 71, 71, (34, 38))\n",
      "(49, 148, 37, 74, (1, 7))\n",
      "(51, 154, 77, 77, (2, 7))\n",
      "(53, 160, 5, 80, (1, 2))\n",
      "(55, 166, 83, 83, (3, 41))\n",
      "(57, 172, 43, 86, (1, 10))\n",
      "(59, 178, 89, 89, (4, 10))\n",
      "(61, 184, 23, 92, (1, 5))\n",
      "(63, 190, 95, 95, (34, 39))\n",
      "(65, 196, 49, 98, (1, 8))\n",
      "(67, 202, 101, 101, (2, 8))\n",
      "(69, 208, 13, 104, (1, 3))\n",
      "(71, 214, 107, 107, (32, 37))\n",
      "(73, 220, 55, 110, (1, 42))\n",
      "(75, 226, 113, 113, (3, 3))\n",
      "(77, 232, 29, 116, (1, 6))\n",
      "(79, 238, 119, 119, (5, 11))\n",
      "(81, 244, 61, 122, (1, 6))\n",
      "(83, 250, 125, 125, (2, 40))\n",
      "(85, 256, 1, 128, (1, 1))\n",
      "(87, 262, 131, 131, (3, 9))\n",
      "(89, 268, 67, 134, (1, 9))\n",
      "(91, 274, 137, 137, (28, 33))\n",
      "(93, 280, 35, 140, (1, 4))\n",
      "(95, 286, 143, 143, (5, 38))\n",
      "(97, 292, 73, 146, (1, 43))\n",
      "(99, 298, 149, 149, (2, 7))\n",
      "(101, 304, 19, 152, (1, 7))\n",
      "(103, 310, 155, 155, (26, 31))\n",
      "(105, 316, 79, 158, (1, 12))\n",
      "(107, 322, 161, 161, (3, 36))\n",
      "(109, 328, 41, 164, (1, 41))\n",
      "(111, 334, 167, 167, (19, 24))\n",
      "(113, 340, 85, 170, (1, 2))\n",
      "(115, 346, 173, 173, (2, 10))\n",
      "(117, 352, 11, 176, (1, 5))\n",
      "(119, 358, 179, 179, (3, 10))\n"
     ]
    }
   ],
   "source": [
    "n=1\n",
    "while n<120:\n",
    "    result=(n,f(n),g(n),(3*n+1)/2,s(n))\n",
    "    print(result)\n",
    "    n+=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(27, 82, 41, 41, (37, 41))\n",
      "(31, 94, 47, 47, (35, 39))\n"
     ]
    }
   ],
   "source": [
    "n=1\n",
    "while n<2000000:\n",
    "    sd=s(n)\n",
    "    result=(n,f(n),g(n),(3*n+1)/2,sd)\n",
    "    if(sd[0]>=n):\n",
    "        print(result)\n",
    "    n+=2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "```\n",
    "1. 首先, 当n满足 `3*n+1 == 2^y` 即 `n=(2^(2*k)-1)/3`, g(n)都会直接返回1, 这也是根节点1的全部子节点，这个数列具有递推函数 h(x)=4*x+1\n",
    "2. 接着，考察5的子节点，第一个子节点是3, 通过v(5)= (2*5-1)/3 生成,\n",
    "其余小兄弟之间 还是具有递推关系 h(x)=4*x+1\n",
    "3. 考虑3的倍数, 因为 (3*n+1)/2^y %3 = 2^(-y)%3 == 1 or 2, 所以任意3的倍数都是叶节点。\n",
    "4. 继续，考察85的子节点，第一个子节点是113，通过v(85)= (4*85-1)/3 生成\n",
    "...\n",
    "\n",
    "1 \n",
    "1,5,21,85,341, ..., a[k]= (2^(2*k)-1)/3=(4^k-1)/3; a[k]= (4*(a[k-1]*3+1) -1)/3=4*a[k-1]+1, for k=1,2,3,... h(x)=4*x+1\n",
    "\n",
    "5<--3,v(x)= (2*x-1)/3 if(x%3==2); b[k]=(2*a[k]-1)/3=4^k*2/9 - 5/9, for k=2,6,10,14,...\n",
    "5<--3,13,53,..., h(x)=4*x+1\n",
    "\n",
    "21  \n",
    "85<--113,v(x)=(4*x-1)/3 elif(x%3==1) ; c[k]=(4*x-1)/3 = 4^k*16/9-7/9, for k=4,8,12,16,...\n",
    "85<--113,453,1813, ..., h(x)=4*x+1\n",
    "\n",
    "h(x)=4*x+1;\n",
    "v(x)= (2*x-1)/3 if(x%3==2);\n",
    "v(x)=(4*x-1)/3 elif(x%3==1);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "(2019-10-28) 我在探索分析Collatz-Odd-Tree时, 发现了Collatz猜想的一个绝妙证明! 也许能让Thwaites欣赏并在2019奖励我£1000。\n",
    "请看, 3n+1猜想证法2：\n",
    "\n",
    "定义 **Collatz 正奇数回归树(Collatz-Odd-Tree)** : 对于任意正奇数 n=2k+1, n 是 g(n)的子节点, g(n)<--n . 或者称之为根节点为1的 **Collatz逆向生成树** .\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Collatz正奇数回归树生成规则(Collatz-Odd-Tree Generation Rule)**:\n",
    "\n",
    "1. 每个节点的长子由 `v(x)=(2*x-1)/3 or (4*x-1)/3` 产生\n",
    "2. 其余每个小兄弟由 `h(x)=4*x+1` 迭代陆续产生\n",
    "3. x在完全的Collatz-Odd-Tree中是叶节点 iff (x%3==0)\n",
    "\n",
    "证明3n+1猜想成立也就只需证明Collatz-Odd-Tree中逆向生成了所有的正奇数。\n",
    "显然，从`x0=1`出发，通过 `h(x)=4*x+1` 和 `v(x)=(2*x-1)/3 or (4*x-1)/3` 反复迭代，会生成所有形如4k+1和4k-1的数，即所有正奇数。Collatz猜想证明完毕□"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "References:  \n",
    "1. https://en.wikipedia.org/wiki/Collatz_conjecture\n",
    "2. https://www.dcode.fr/collatz-conjecture\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath (stable)",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}